package ClassicDataStructuresAndAlgorithms.ClassicLinkedListAlgorithms;

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

/**
 * 把这道题转换成合并K个有序链表的题目
 *  nums1 = [1,7,11], nums2 = [2,4,6]
 *  转换成
 *  [1,2]->[1,4]->[1,6]
 *  [7,2]->[7,4]->[7,6]
 *  [11,2]->[11,4]->[11,6]
 */

public class Solution373 {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        //我们使用三元组（nums[i],nums[j],j）来记录每个结点
        //其中j用来将下一个元素放入优先级队列
        PriorityQueue<int[]> pq = new PriorityQueue<>(
                (a,b)->{
                    return (a[0]+a[1])-(b[0]+b[1]);
                }
        );

        //将每个链表的head放入小顶堆当中
        for (int i = 0; i < nums1.length; i++) {
            pq.offer(new int[]{nums1[i],nums2[0],0});
        }

        //开始从堆中依次取出元素，并放入res当中
        List<List<Integer>> res = new ArrayList<>();

        while(pq!=null && k>0){
            //cur临时接收弹出的结点
            int[] cur = pq.poll();
            //在插入下一位元素时，cur[0]不会变，下一个结点的cur[0]的值依旧。
            //而cur[1]的值会变，成为nums[next_index]
            int next_index = cur[2]+1;
            //下一个node进入堆
            if (next_index < nums2.length) {
                pq.offer(new int[]{cur[0],nums2[next_index],next_index});
            }

            //将cur放入结果集中
            List<Integer> result = new ArrayList<>();
            result.add(cur[0]);
            result.add(cur[1]);
            res.add(result);
            k--;
        }

        return res;
    }
}
